In the field of digital systems design, considerable efforts have been directed towards shortening-development cycles. One of the significant factors in the length of such product-development cycles is the time required for the design and fabrication of digital integrated circuits (IC's). Once a circuit design is completed, it generally takes at least four weeks, and often several months, to fabricate a silicon version of the circuit in a "chip." To reduce the design and fabrication interval, attempts have been made to provide various types of user-definable, or programmable, logic devices (PLD's).
PLD's include devices that are fusible, as well as those that are electrically-programmable and reprogrammable, such as the reprogrammable gate arrays described in my U.S. Pat. No. 4,700,187 for "Programmable, Asynchronous Logic Cell and Array". The reprogrammable devices are sometimes called "erasable, programmable logic devices," or EPLD's. Since an EPLD can be programmed more than once, an error in programming can be corrected by simply reprogramming the device. Further, the entire device can be fully, nondestructively tested at the factory. Such testing is independent of any device application and therefore need not be the user's responsibility.
In general, an EPLD comprises an array of logic elements and programmable means for interconnecting those elements. The most common earlier approaches in programmable logic devices, and a currently leading approach in EPLD's, employ variations of the programmable logic array (PLA) architecture, which is composed of an AND-array connected to an OR-array. Most PLD's add to these arrays input and output blocks containing registers, latches and feedback paths. The connections between the AND and OR arrays are programmable, as are the input and output blocks and feedback paths. Programmability of these connections is achieved through the use of fusible links, EPROM cells, EEPROM cells or static RAM cells.
Illustrative papers describing what are now referred to as EPLD's are S. N. Kukreja et al., "Combinational and Sequential Cellular Structures", IEEE Trans. on Computers, Vol. C-22, No. 9, p. 813 (September 1973) and F. B. Manning, "An Approach to Highly Integrated, Computer Maintained Cellular Arrays," IEEE Trans. on Computers, Vol. 26, No. 6, p. 536 (June 1977).
Typical commercial EPLD's include the Logic Cell Array (a trademark) from Xilinx, Inc. which is described more fully in The Programmable Gate Array Data Book (Xilinx, 1988). Xilinx and other companies market EPLD's and associated development systems which provide tools to aid in the design of logic systems employing their respective programmable devices.
Design entry in these products is accomplished by one of four methods: (1) schematic input of the logic circuit; (2) net list entry, by which the user enters the design by describing symbols and interconnections in words, following a standardized format; (3) state equation/diagram entry; and (4) Boolean equations. Intel's development system converts all design entry data into Boolean equations which are then converted to a sum-of-products format after logic reduction. The configurable logic block used in the Xilinx product is programmed either by the entry of Boolean equations or by the entry of a Karnaugh map.
While these EPLD architectures may represent an advance over prior logic systems which did not provide user programmability, they are far from ideal. Design entry requires the user to have extensive training in digital logic design. This, of course, limits the user base. And none of these approaches provides a tool for the modular, hierarchical design of complex circuits. Other deficiencies will be apparent to those skilled in the art.
Improvements over these EPLD's are achieved by logic arrays described in my U.S. patent application No. 06/928,527 for "Programmable Logic cell and Array." That application describes the use of programmable logic cells, and arrays of those cells, having, inter alia, the following characteristics: (1) the ability to program each cell to act either as a logic element or as one or more logical "wire" elements (i.e.) identity functions between one or more specified inputs and one or more specified outputs of the cell--these identity functions include crossovers, bends, fan-outs, and routings running both horizontally and vertically); (2) the ability to rotate programmed circuits (through 90.degree. increments) and to reflect programmed circuits about horizontal and vertical axes; (3) an integrated logic and communication structure which emphasizes local communications; (4) a simple structure at the cell level, thereby making available a very fine-grained logic structure, and (5) suitability for implementation of both synchronous and asynchronous logic, including speed-independent circuits.
In an exemplary implementation, each cell has two inputs and two outputs, allowing the cells to be arranged in a grid such that each cell communicates one way with its north, east, south and west neighbors. The cells are programmable to assume any one of several states, to provide the foregoing characteristics.
Such arrays of cells are well-suited to implementation in an integrated circuit "chip" using modern, very-large-scale integration (VLSI). On a chip, the logical wiring capabilities of the cells make it possible to "wire around" defective cells and elements. Thus, the invention shows promise for so-called "wafer-scale" integration or fabrication. If a large wafer contains a few defective cells, those cells can simply be avoided and bypassed, with the remainder of the wafer remaining useful. This may permit the fabrication of much larger chips than has heretofore been possible, since defects normally render a chip useless.
These chips can themselves be assembled into arrays and other configurations. Such an arrangement of cells (whether disposed on one or more chips) may be referred to as a "medium." For contrast and clarity of expression, an array of chips will be referred to hereinafter as a "matrix," to distinguish it from an array of cells. A matrix of chips can be extended freely in any dimension desired. Thus, computing power can be increased by simply adding more chips to the matrix.
As indicated in the '527 Application, the basic logic cell is programmable and reprogrammable in accordance with existing technology adaptable to that purpose. Programming is accomplished by setting the states of an appropriate number of storage (i.e., memory) elements associated with each cell. In a first exemplary embodiment, the cells may be composed of NOR gates, transistor switches and gain elements for driving adjacent cells. In this way each cell may be individually programmed so that different cells on the same chip have the same or different functions as the need arises. Thus, different cells on the same chip may be operated in parallel with one another or they may be operated independently of each other.
Using a programming system such as the exemplary graphical programming environment described in the '527 Application, the individual logic cells may be programmed and connected together to implement an extensive class of logic circuits. Configuration specifications for (i.e. programs for setting cell storage elements to create) circuit blocks such as adders, multiplexers, buffer stacks, and so forth, may be stored in a library for use in building more complex blocks. With an adequate library, custom hardware can be designed by simply mapping stored blocks onto selected portions of chips (i.e., the medium) and connecting the blocks together. In particular, in the mapping operation, a configuration that is stored in the library is used to specify the states of the storage elements associated with the logic cells needed to define the desired circuit. This generates a tremendous savings in the time required for the development of many types of application-specific integrated circuits (ASIC's). Moreover, this approach allows the designer to construct systems at a pictorial block-diagram level, as well as at the circuit, or detailed logic level.
Further, as described in conjunction with Figs. 16-24 of the '527 application, blocks retrieved from the library may be moved, rotated, or reflected about a horizontal or vertical axis, to place their specification of input and output connections on different sides and positions without altering the internal electrical operation specified by the block. This capability allows the user to (1) construct systems at a pictorial block-diagram level without having to be concerned about the internal structure of each block and (2) create large blocks from smaller blocks, the larger blocks also being storable in the library for recall and for use in creating even larger blocks. Further, it enhances the designer's freedom in laying out a chip design, and reduces the size of the block-function library needed for any particular application.